'''
https://leetcode.cn/problems/regular-expression-matching/description/
'''
from functools import cache


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        @cache
        def f(i, j):
            if i == m:
                # s完了
                # 1) p也完了
                # 2) p没完。p后边必须是a*这种结构
                return j == n or (j + 1 < n and p[j + 1] == '*' and f(i, j + 2))
            elif j == n:
                # p完了，s没完
                return False
            else:
                if j + 1 == n or p[j + 1] != '*':
                    # 普通位置必须匹配
                    return (s[i] == p[j] or p[j] == '.') and f(i + 1, j + 1)
                else:
                    # p下一个位置是*
                    # 1) pass
                    p1 = f(i, j + 2)
                    # 2) 能匹配的情况下匹配，但p别着急走，说不定还能继续匹配
                    p2 = (s[i] == p[j] or p[j] == '.') and f(i + 1, j)
                    return p1 or p2

        return f(0, 0)

    def isMatch2(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        @cache
        def f(i, j):
            if i == m:
                return j == n or (j + 1 < n and p[j + 1] == '*' and f(i, j + 2))
            elif j == n:
                return False
            else:
                if j + 1 == n or p[j + 1] != '*':
                    return (s[i] == p[j] or p[j] == '.') and f(i + 1, j + 1)
                else:
                    p1 = f(i, j + 2)
                    p2 = (s[i] == p[j] or p[j] == '.') and f(i + 1, j)
                    return p1 or p2

        return f(0, 0)

    # 打表
    def isMatch3(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        # 第一维度依赖后边的，第二维度依赖后边的
        # 依赖 1.右边 2.右下 3，下
        dp[m][n] = True
        for j in range(n - 2, -1, -1):
            # (j + 1 < n and p[j + 1] == '*' and f(i, j + 2))
            dp[m][j] = p[j + 1] == '*' and dp[m][j + 2]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if j + 1 == n or p[j + 1] != '*':
                    dp[i][j] = (s[i] == p[j] or p[j] == '.') and dp[i + 1][j + 1]
                else:
                    p1 = dp[i][j + 2]
                    p2 = (s[i] == p[j] or p[j] == '.') and dp[i + 1][j]
                    dp[i][j] = p1 or p2
        return dp[0][0]

    def isMatch4(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        @cache
        def f(i, j):
            if i < 0:
                return j < 0 or (p[j] == '*' and f(i, j - 2))
            elif j < 0:
                return False
            else:
                if p[j] == '*':
                    p1 = f(i, j - 2)
                    p2 = (s[i] == p[j - 1] or p[j - 1] == '.') and f(i - 1, j)
                    return p1 or p2
                else:
                    return (s[i] == p[j] or p[j] == '.') and f(i - 1, j - 1)
        return f(m-1, n-1)
